package com.maduar.demo.tree;

import org.springframework.util.CollectionUtils;

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

/**
 * Description:
 *
 * @author maduar maduar@163.com
 * @date 2021-05-18 22:27
 */
public class BinaryTree {

    Node root;

    public static BinaryTree getInstance(List<Integer> list) {
        return getInstance(list, null);
    }

    public static BinaryTree getInstance(List<Integer> list, BinaryTree binaryTree) {
        if (Objects.isNull(binaryTree)) {
            binaryTree = new BinaryTree();
        }

        if (CollectionUtils.isEmpty(list)) {
            return binaryTree;
        }

        for (Integer value : list) {
            binaryTree.add(value);
        }

        return binaryTree;
    }

    public void add(int value) {
        root = addRecursive(root, value);
    }

    private Node addRecursive(Node current, int value) {
        if (Objects.isNull(current)) {
            return new Node(value);
        }

        if (value < current.value) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = addRecursive(current.right, value);
        } else {
            // values already exists
            return current;
        }

        return current;
    }

    private boolean containsNodeRecursive(Node current, int value) {
        if (Objects.isNull(current)) {
            return false;
        }

        if (value == current.value) {
            return true;
        }

        return value > current.value
                ? containsNodeRecursive(current.right, value)
                : containsNodeRecursive(current.left, value);

    }

    public boolean containsNodeRecursive(int value) {
        return containsNodeRecursive(root, value);
    }

    private Node deleteRecursive(Node current, int value) {
        if (Objects.isNull(current)) {
            return null;
        }

        if (value == current.value) {
            if (Objects.isNull(current.left) && Objects.isNull(current.right)) {
                return null;
            }

            if (Objects.isNull(current.left)) {
                return current.right;
            }

            if (Objects.isNull(current.right)) {
                return current.left;
            }
        }

        if (value < current.value) {
            current.left = deleteRecursive(current.left, value);
            return current;
        } else {
            current.right = deleteRecursive(current.right, value);
            return current.right;
        }
    }

    public void deleteRecursive(int value) {
        root = deleteRecursive(root, value);
    }

    public void travereInOrder() {
        travereInOrder(root);
    }

    public void travereInOrderNotRecursive() {
        if (Objects.isNull(root)) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Node current = root;
        while (Objects.nonNull(current) || !stack.isEmpty()) {
            while (Objects.nonNull(current)) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            System.out.print(current.value + " ");
            current = current.right;
        }
    }

//    public void traverePreOrderNotRecursive() {
//        if (Objects.isNull(root)) {
//            return;
//        }
//
//        Stack<Node> stack = new Stack<>();
//        Node current = root;
//        while (Objects.nonNull(current) || !stack.isEmpty()) {
//            System.out.print(current.value + " ");
//            while (Objects.nonNull(current)) {
//                stack.push(current);
//                current = current.left;
//            }
//
//            current = stack.pop();
//            current = current.right;
//        }
//    }

    private void travereInOrder(Node node) {
        if (Objects.nonNull(node)) {
            travereInOrder(node.left);
            System.out.print(" " + node.value);
            travereInOrder(node.right);
        }
    }

    public void traverePreOrder() {
        traverePreOrder(root);
    }

    private void traverePreOrder(Node node) {
        if (Objects.nonNull(node)) {
            System.out.print(" " + node.value);
            traverePreOrder(node.left);
            traverePreOrder(node.right);
        }
    }

    public void traverePostOrder() {
        traverePostOrder(root);
    }

    private void traverePostOrder(Node node) {
        if (Objects.nonNull(node)) {
            traverePostOrder(node.left);
            traverePostOrder(node.right);
            System.out.print(" " + node.value);
        }
    }

    public void travereLevelOrder() {
        if (Objects.isNull(root)) {
            return;
        }

        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);

        while (!nodes.isEmpty()) {
            Node node = nodes.remove();
            System.out.print(" " + node.value);
            if (Objects.nonNull(node.left)) {
                nodes.add(node.left);
            }

            if (Objects.nonNull(node.right)) {
                nodes.add(node.right);
            }
        }
    }

    public int findSmallestValue() {
        return findSmallestValue(root);
    }

    private int findSmallestValue(Node current) {
        return Objects.isNull(current.left)
                ? current.value
                : findSmallestValue(current.left);
    }

    public int findBigestValue() {
        return findBigestValue(root);
    }

    private int findBigestValue(Node current) {
        return Objects.isNull(current.right)
                ? current.value
                : findBigestValue(current.right);
    }

    class Node{
        int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
}
